ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group97a.txt/000050_icon-group-sender _Wed Feb 26 08:17:18 1997.msg

Internet Message Format | 2000-09-20 | 10KB

Received: by cheltenham.cs.arizona.edu; Thu, 27 Feb 1997 09:03:58 MST
To: [e-mail]
Date: Wed, 26 Feb 1997 08:17:18 -0500
From: Jan Galkowski <[e-mail]>
Message-Id: <[e-mail]>
Organization: Digicomp Research Corporation
Sender: [e-mail]
Subject: Icon and two-dimensional matching
Errors-To: [e-mail]
Status: RO
Content-Length: 9732

[LONG post warning!]

One of the things that strikes me from the partial set of responses
I've gotten regarding my queries "What's the largest Icon program
you've written?" and related, is the extent to which these reported
uses of Icon are examples of "new wines in old bottles".  That is to
say, the applications remain pretty traditional, although Icon brings
its own means and methods to these problems.

Now, I don't in any way want to depreciate or criticize the use or
power of Icon in traditional programming.  Indeed, seeing how
traditional problems can be addressed by new methods and
expressive styles is crucial to developing programming itself.
While the conceptual algorithm for expression may be about the
same, the means used to realize it  with the "generate and test" mindset
available in Icon can be dramatically different than in, say, Ada.
Moreover, there are some algorithms which, because of the
availability of Icon's tables, may now be usable and practical
because the effort to use these elements is negligible compared to,
again say, Ada since their one might need to implement the
elements.  It is important to continuously reconsider putting
new wines in "old bottles" if the depth of our collective craft
is to be maintained.


Still, I wonder if use of Icon would be invigorated if we, collectively,
tried to push it into new areas, ones where it may well have an
edge on traditional software solutions.  For example, the current
(March 1997) issue of _Scientific_ _American_ reports in part
(see pages 54-55) that finding and decoding graphical pictures is
a big part of the technical frontier for Web crawlers.  Putting
aside the extremely thorny problem of dealing with natural
images (the kind off of a camera or TV screen), consider the
set of images which are generated by graphics facilities of
applications or programming languages such as the graphics
facilities of Icon.  (Professor Griswold and company are
working a book just addressing these facilities.)   Then,
perhaps, finesse how to get these images into some
symbolic form and consider the problem of matching patterns
within these images using some two-dimensional analog to
Icon's matching facilities.  What can be developed there?
I think there's a practical motivation, but I suspect in this
initial search it's counterproductive to limit oneself to
just the practical.  Let this be a kind of brain teaser, and
let's leave it as motivated purely for fun.

Well, let's consider some of the literature on this.

People have considered various kinds of two dimensional
automata.  These could form the mechanical metaphor for
a two-dimensional scanner.  Basically, the analog to a
Turing machine of sorts is a scanner which can move at
one step in any of four orthogonal directions, north, south,
west, or east.  It can tell the state of a cell it is over,
basically what it contains, and it can write into that cell.
It's also possible to "mark" cells with annotations that don't
overwrite their contents.  I recall a good conceptual
description of such a machine in the second or third edition
of the neat little book _Perceptrons_ by Marvin Minsky and
Seymour Paper, quoting work by Blum, although their interest
is getting at the computational basics of understanding
natural images.  One could imagine a set of facilities analogous
to Icon's _move_, _tab_, _find_, _match_, "?", and some
2D equivalent to csets working in two dimensions, at least
plausibly.

Although they don't seem sufficiently powerful to deal with
natural imagery, people have explored various kinds of
2D grammars.  These are often studied and presented in the
context of production of patterns and textures, but we might
consider them for recognition and parsing.

There are, for example, _shape_ _grammars_ proposed by
G.Stiny and J.Gips (_Algorithmic_ _Aesthetics_: _Computer_
_Models_ _for_ _Criticism_ _and_ _Design_ _in_ _the_
_Arts_, University of California Press, Berkeley, 1972, as
reported in D.Ballard, C.Brown, _Computer_ _Vision_, 1982,
pp. 173-175) which are used to generate textures.

There are tree grammars (see S.Y.Lu, K.S.Fu, "A syntactic
approach to texture analysis," _Computer_ _Graphics_ _and_
_Image_ _Processing_, vol. 7, no. 3, June 1978, pp. 303-330,
also summarized in Ballard and Brown, pp. 175-178) which
apply pyramids to the description of tesselations.  Milgram and
Rosenfeld ("Array automata and array grammars", Proceedings,
IFIP Congress 71, Booklet TA-2, Amsterdam: North-Holland,
1971, 166-173, also described on pp. 178-181 of Ballard and
Brown) which use two-dimensional "atoms" to generate patterns
from symbols.  (The term "atom" is used in the sense it is in
LISP, as a basic elementary symbol which cannot be
deconstructed, at least "using ordinary chemical means".)

Finally, in modeling regions and pictures, Rosenfeld and Kak
give a moderately lengthy and technical presentation on
grammars in their volume 2 of _Digital_ _Picture_ _Processing_
(Academic Press, 1982, pp. 317-327).

A little description of shape grammars will illustrate how this tends
to go:

Suppose one is given,

    First, a finite set of shapes, Vt.  Members of Vt are "terminal
elements" or basic symbols.

    Second, a finite set of symbols, Vm.  Members of Vm are
"nonterminal shape elements" or markets.  Vm and Vt are
disjoint.

    Third, a set Vt+ consisting of elements formed by the "finite
arrangement of one or more elements of Vt in which any elements
and/or their mirror images may be used a multiple number of
times in any location, orientation, or scale" (Ballard, Brown,
page 173).  This is complicated.  We could just as well enhance
Vt to consist of a basic symbol and basic symbols generated
from that one by rotation, reflection, and scaling.  I like that
way of doing this better.

    Fourth, a set Vt* which consists of Vt+ and the empty shape.

   Fifth, a set Vm+ defined from Vm in the manner Vt+ is defined
from Vt.

   Sixth, a set Vm* which consists of Vm+ and the empty shape.

   Seventh, a finite set R of ordered triples (u,v,w) such that u is
a shape consistning of elements of Vm+, v is an element of
Vt*, and w is an element of Vm*.  Each of these triples is
called a "shape rule" where u is the left side of the rule,
and v an w together form the right side of the rule.

A texture is generated from a shape grammar by beginning with
some initial shape and repeatedly apply the shape rules wherever
they can be applied.  The elementary step of applying a particular
shape rule (u,v,w) to some shape S is S with the right side (v and w
concatenated) substituted for an occurence in the former S of an
instance of u.

The iteration which does this can be sketched:


   1. Find part of the shape in question which is geometrically
      similar to the left side of a rule in therms of both terminal
      elements and nonterminal elements.  There must be a
      1-1 correspondence between the terminals and markers
      on the LHS of the rule and the terminals and markers in the
      part of the shape in question to which the rule is to
      be applied.  Deal with multiple matching rules in some
      way (a conflict resolution strategy), perhaps by letting
      _all_ rules produce daughter shapes concurrently and
      in different contexts.

  2. Find the geometric transformations such as scaling,
     local translation, rotation, reflection which make the LHS
     of the rule identical to the corresponding part in the shape
     in question.

 3. Apply these same transformations to the RHS of the
    matching rule.

 4. Substitute the transformed RHS of the rule for the part of
    the shape that corresponds to the LHS of the rule.

The generation process terminates when no rule in the grammar
can be applied.

Ballard and Brown given an example of how the shape grammar
can generate the hexagonal tesselation of the plane:


      Vt consists of a single hexagon of a fixed size (for brevity,
       call this symbol "H")

      Vm consists of a single nonterminal, "o", say called a "dot".

      R consists of the rules

                             o
            H o --->  H     H

            H o --->  H   o H

            H o --->  H     H o

                           o
            H o --->  H     H

            H o --->  H     H
                             o

            H o --->  H     H
                           o


where basically one template instance of "H" with a dot
adjacent produces all configurations of the dot about
the hexagonal element, that is, one placement on each
of its six sides.

Recognition of a texture involves deconstruction of the
pattern using the rules in the reverse direction.  If there is
but a single nonterminal left in the procedure, the shape is
said to be recognized, and its identity is given by the
identity of the nonterminal.

OK.  So what could be done with Icon?  I'm not at all proposing
extensions or changes to the language at all.  Let's just consider
it a programming exercise and challenge.  If we wanted to write
Icon programs to parse two dimensional symbol structures, how
would we go about it?   Well, we need to place indices in some
canonical way, and we need to have a means of stepping from
one (i,j) configuration to another.  How do we describe two
dimensional shape patterns?  Suppose, for the moment,  the array
 we want to do matching in can have on ASCII characters
as elements.  Clearly, later we could expand the definition of
csets to contain various graphical elements such as oriented
lines, etc.

-
 Jan Theodore Galkowski,
    Developer, tool & numerical methods elf
 Digicomp Research Corporation,
 Ithaca, NY 14850-5720

  [e-mail]